// 栈
// "消消乐" 问题，要想到使用栈的思想解决
// 表达式求值问题 - 使用栈模拟计算过程，栈是一种思想，不局限于形式（可以是 stringBuilder， 也可以是 数组）
// 带括号的表达式 - 一般都需要用到双栈进行模拟

// 例题 4：
// 给定一个经过编码的字符串，返回它解码后的字符串。
// 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
// 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
// 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
//
//        示例 1：
//
//        输入：s = "3[a]2[bc]"
//        输出："aaabcbc"
//        示例 2：
//
//        输入：s = "3[a2[c]]"
//        输出："accaccacc"
//        示例 3：
//
//        输入：s = "2[abc]3[cd]ef"
//        输出："abcabccdcdcdef"
//        示例 4：
//
//        输入：s = "abc3[cd]xyz"
//        输出："abccdcdcdxyz"
//
//
//        提示：
//
//        1 <= s.length <= 30
//        s 由小写英文字母、数字和方括号 '[]' 组成
//        s 保证是一个 有效 的输入。
//        s 中所有整数的取值范围为 [1, 300]

// 解题思路：
// 带括号的字符串表达式，一般都需要使用双栈进行模拟
// 一个栈用于记录数字，另一个栈用于记录字符串
// 遇到数字，找全部数字放进数字栈
// 遇到左括号，找括号里的字符串放进字符串栈，如果括号里没有字符串，那么就把空串放进字符串栈
// 遇到右括号，就把 数字栈 和 字符串栈 中的栈顶元素拿出来解析，解析完放到栈顶元素的后面
// 遇到直接字符串，直接放到栈顶元素的后面

import java.util.Stack;

public class DecodeString {
    public String decodeString(String s) {
        int n = s.length();
        char[] sArr = s.toCharArray();
        Stack<Integer> stack1 = new Stack<>();
        Stack<String> stack2 = new Stack<>();
        stack2.push("");
        int i = 0;
        while(i < n){
            if(sArr[i] >= '0' && sArr[i] <= '9'){
                int tmp = 0;
                while(i < n && sArr[i] >= '0' && sArr[i] <= '9'){
                    tmp *= 10;
                    tmp += sArr[i] - '0';
                    i++;
                }
                stack1.push(tmp);
            }else if(sArr[i] == '['){
                i++;
                StringBuilder tmp = new StringBuilder();
                while(i < n && sArr[i] >= 'a' && sArr[i] <= 'z'){
                    tmp.append(sArr[i]);
                    i++;
                }
                stack2.push(tmp.toString());
            } else if(sArr[i] >= 'a' && sArr[i] <= 'z'){
                StringBuilder tmp = new StringBuilder();
                while(i < n && sArr[i] >= 'a' && sArr[i] <= 'z'){
                    tmp.append(sArr[i]);
                    i++;
                }
                String t = stack2.pop();
                stack2.push(t + tmp.toString());
            }else{
                int num = stack1.pop();
                String tmp = stack2.pop();
                String t = stack2.pop();
                for(int j = 0; j < num; j++) t += tmp;
                stack2.push(t);
                i++;
            }
        }
        return stack2.peek();
    }
}
